package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC773 {

//    int MAX_STEP = 100;
//
//    // 记录一维字符串的相邻索引
//    int[][] neighbor = {
//            {1, 3},
//            {0, 4, 2},
//            {1, 5},
//            {0, 4},
//            {3, 1, 5},
//            {4, 2}
//    };
//
//    public int slidingPuzzle(int[][] board) {
//        int m = 2, n = 3;
//        int[] start = new int[6];
//        int startIndex = -1;
//        // 将 2x3 的数组转化成字符串
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                start[i * 3 + j] = board[i][j];
//                if (board[i][j] == 0) {
//                    startIndex = i * 3 + j;
//                }
//            }
//        }
//
//        Set<String> visitedPath = new HashSet<>();
//        visitedPath.add(toStr(start));
//        return recurDepth(start, startIndex, visitedPath);
//    }
//
//    public int recurDepth(int[] curStr, int startIndex, Set<String> visitedPath) {
//        if (toStr(curStr).equals("123450")) {
//            return 0;
//        }
//
//        int curMinPath = MAX_STEP;
//        int[] neighborArray = neighbor[startIndex];
//        for (int ni : neighborArray) {
//            swap(curStr, startIndex, ni);
//            String curPath = toStr(curStr);
//            if (visitedPath.contains(curPath)) {
//                continue;
//            }
//
//            visitedPath.add(curPath);
//            int nextDepth = recurDepth(copyNewArray(curStr), ni, visitedPath) + 1;
//            if (nextDepth < curMinPath) {
//                curMinPath = nextDepth;
//            }
//
//            swap(curStr, startIndex, ni);
//        }
//
//        return curMinPath;
//    }
//
//    public int[] copyNewArray(int[] str) {
//        int[] newStr = new int[str.length];
//        for (int i = 0; i < str.length; i++) {
//            newStr[i] = str[i];
//        }
//        return newStr;
//    }
//
//    public String toStr(int[] str) {
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < 6; i++) {
//            sb.append((char) (str[i] + '0'));
//        }
//
//        return sb.toString();
//    }
//
//    public void swap(int[] str, int i, int j) {
//        int temp = str[i];
//        str[i] = str[j];
//        str[j] = temp;
//    }

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 上述代码之所以无法正常工作，是因为妄图使用DFS搜索最短路径，并且使用DFS方法不对
     * 图中搜索最短路径优先选择则BFS，如下述代码
     * 具体搜索路径，DFS和BFS的区别，详见文档：https://blog.csdn.net/Dog_dream/article/details/80270398
     * @return:
     */

    public int slidingPuzzle(int[][] board) {
        Queue<String> queue = new LinkedList<>();
        // visited的key记录已经访问过的状态，value记录从初始状态要走多少步到达当前状态
        Map<String, Integer> visited = new HashMap<>();

        String init = boardToString(board);
        // 如果初始状态就是目标状态，那直接返回0
        if (init.equals("123450")) {
            return 0;
        }

        queue.offer(init);
        visited.put(init, 0);

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            List<String> nexts = getNexts(cur);

            for (String next : nexts) {
                if (!visited.containsKey(next)) {
                    // 如果cur的某个邻居就是目标状态，直接返回路径长度
                    if (next.equals("123450")) {
                        return visited.get(cur) + 1;
                    }

                    queue.offer(next);
                    visited.put(next, visited.get(cur) + 1);
                }
            }
        }

        return -1;
    }

    // 计算状态s的邻居状态
    private List<String> getNexts(String s) {
        // 先将s转化为盘面
        int[][] cur = stringToBoard(s);
        // 接下来先找0
        int zero;
        for (zero = 0; zero < 6; zero++) {
            if (cur[zero / 3][zero % 3] == 0) {
                break;
            }
        }
        // 开个二维数组表示四个相邻的方向
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        // 存储邻居状态
        List<String> res = new ArrayList<>();
        int zx = zero / 3, zy = zero % 3;
        for (int i = 0; i < 4; i++) {
            int nextx = zx + dirs[i][0], nexty = zy + dirs[i][1];
            if (inBoard(nextx, nexty)) {
                // 交换0和邻居，得到新的状态
                swap(cur, zx, zy, nextx, nexty);
                res.add(boardToString(cur));
                // 注意，一定恢复成原来的状态，然后再产生下一个状态
                swap(cur, zx, zy, nextx, nexty);
            }
        }

        return res;
    }

    private void swap(int[][] board, int x1, int y1, int x2, int y2) {
        int tmp = board[x1][y1];
        board[x1][y1] = board[x2][y2];
        board[x2][y2] = tmp;
    }

    private boolean inBoard(int x, int y) {
        return 0 <= x && x < 2 && 0 <= y && y < 3;
    }

    private int[][] stringToBoard(String s) {
        int[][] board = new int[2][3];
        for (int i = 0; i < s.length(); i++) {
            board[i / 3][i % 3] = s.charAt(i) - '0';
        }
        return board;
    }

    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                sb.append(board[i][j]);
            }
        }

        return sb.toString();
    }


    public static void main(String[] args) {
        LC773 an = new LC773();

        int[][] arr = InputUtil.toDoubleIntegerArray("[[4,1,2],[5,0,3]]");
        System.out.println(an.slidingPuzzle(arr));
    }
}
